1. Field
Embodiments relate to a path planning apparatus and method of a robot to plan an optimal path along which a manipulator of the robot moves to a goal point from a start point.
2. Description of the Related Art
Generally, a robot refers to an apparatus performing motion similar to human operation using electric or magnetic work. Earlier robots were industrial robots, such as manipulators or transfer robots used for work automation, or unmanned systems and have carried out dangerous work, simple repeated work, or work requiring a great amount of force. Recently, research has been actively conducted into a humanoid robot that has a joint system similar to that of humans, lives with humans in a human workplace or residence, and provides various services.
Such a humanoid robot works using a manipulator designed to move similarly to an operation of human arms or hands by an electronic and mechanical mechanism. Most currently used manipulators are configured such that multiple links are connected to each other. A connection part of the links is called a joint. A movement characteristic of the manipulator depends on a geometric relationship between links and joints. Kinematics is the mathematic expression of such a geometric relationship. Most of the manipulators shift a robot end-effector to a goal point to implement work with a kinematic characteristic.
In order for the manipulator to perform given work (e.g., work to grasp an object), it is important to generate a moving path of the manipulator from an initial position (start point) before the manipulator performs work to a final position (goal point) at which the manipulator can perform work, that is, when the manipulator can grasp the object. The moving path of the manipulator, which can move without collision with obstacles within a work area from the start point to the goal point, may be automatically generated by an algorithm. The algorithm may include a process to search for a free space where the manipulator does not collide with obstacles and a process to plan a moving path of the manipulator in the free space. An exemplary embodiment describes a method using a rapidly-exploring random tree (RRT) algorithm in a circumstance having a high degree of freedom or complicated restriction conditions in a sampling based path planning algorithm among path planning methods to plan an optimal path connecting a start point to a goal point while satisfying a restriction condition, such as obstacle avoidance.
The RRT algorithm refers to a method to search for a moving path to a final goal point while extending a tree by repeating a process to select the nearest node from an initial start point using a randomly-sampled configuration in a configuration space (C-space) in which the manipulator performs work. Two methods may be utilized to search for the nearest node: a method using a difference between a goal node and a current node when information about a goal configuration of a final goal point is known, and a method to generate a goal function by a function of a distance and direction vector from a current end effector and a goal end effect and to extend a tree by selecting a node having the least goal function, when information about a goal configuration of a final goal point is known or unknown.
An RRT algorithm using the goal function has been proposed in the case in which a goal configuration is unknown among the conventional RRT algorithms. However, when the RRT algorithm depends greatly on the goal function, if the goal function is not accurately determined, the manipulator may be stuck at local minima and may not obtain a solution. The manipulator may be saved from the local minima by changing the goal function. However, since a tree may be extended in a wrong direction before the manipulator recognizes the local minima, a speed to search for the solution becomes slow and thus considerable time is consumed to search for a path.